---

deArray.hpp

Go to the documentation of this file.

///////////////////////////////////////////////////////////////////////////////
/// @file deArray.hpp
///
/// @brief templated array class
///
/// @author Assassin
///
/// This file is the intellectual property of Novus Delta, LLC.. Usage of the
/// contents of this file is subject to the Destiny3D Member License which
/// can be found at http://www.destiny3d.com.  Any other usage is prohibited.
///
/// This file is distributed "AS IS" without warranty of any kind.  Novus
/// Delta, LLC. does not guarantee the fitness of the contents of this file
/// for any particular purpose.
///
/// Copyright (C) 2001-2003 Novus Delta, LLC. All Rights Reserved.
///
/// <hr>
///                                 Change History
/// <hr>
///
/// @date Sept 2001
/// @author Assassin
/// @remarks Creation
///
/// @date Jan 2002
/// @author Assassin
/// @remarks Bug fixes
///
///////////////////////////////////////////////////////////////////////////////

#ifndef DEARRAY_HPP
#define DEARRAY_HPP

#include "deGlobalTypes.hpp"

#ifndef NULL
#define NULL (0)
#endif
#pragma warning (disable : 4284) // return type for 'identifier::operator –>' is not a UDT or reference to a UDT. Will produce errors if applied using infix notation
#pragma warning (disable : 4710) // function not inlined

template <typename T>
class deTWrapper
{
private:
    T m_data;
public:
    deTWrapper() : m_data() {}
    deTWrapper(const T & ref) : m_data(ref) {}
    virtual ~deTWrapper() {}
    deTWrapper<T>& operator=(const T& ref) { m_data = ref; return *this; }
    deTWrapper<T>& operator=(const deTWrapper<T>& ref) { m_data = ref.m_data; return *this; }
    operator T& () { return m_data; }
    T* operator&() { return &m_data; }
};

/// templated resizable linear array storage class
template <class T>
class deTArray
{
private:
    size_t  m_Length;
    size_t  m_Capacity;
    T*      m_Items;
public:
    static u32 SmallestLargerPow2(u32 x)
    {
        int retval = 1;
        if (x & 0xffff0000)
        { retval += 16; x >>= 16; }
        if (x & 0x0000ff00)
        { retval += 8; x >>= 8; }
        if (x & 0x000000f0)
        { retval += 4; x >>= 4; }
        if (x & 0x0000000c)
        { retval += 2; x >>= 2; }
        if (x & 0x00000002)
        { retval += 1; x >>= 1; }
        return (1 << retval);
    }
#ifdef _DEBUG
    class iterator
    {
    private:
        const deTArray<T>* m_Holder;
        T* m_Ref;
    protected:
        friend class deTArray<T>;
        iterator(T* ref, const deTArray<T>* holder) : m_Ref(ref), m_Holder(holder) {}
    public:
        iterator() : m_Ref(0), m_Holder(0) {}
        ~iterator() {}
        T& operator*() const
        {
            DE_ASSERT (m_Ref >= m_Holder->begin().m_Ref && m_Ref < m_Holder->end().m_Ref);
            return *m_Ref;
        }
        T* operator->() const
        { return &operator*(); }
        void operator++() { ++m_Ref; }
        void operator--() { --m_Ref; }
        bool operator==(const iterator & other) const
        { return m_Ref == other.m_Ref; }
        bool operator!=(const iterator & other) const
        { return m_Ref != other.m_Ref; }
    };
private:
    inline iterator make_iterator(size_t index) const
    {
        return iterator(&m_Items[index], this);
    }
    inline size_t iterator_index(const iterator& it)
    {
        return it.m_Ref - m_Items;
    }
public:
#else
    typedef T* iterator;
private:
    inline iterator make_iterator(size_t index) const
    {
        return &m_Items[index];
    }
    inline size_t iterator_index(const iterator& it)
    {
        return it - m_Items;
    }
public:
#endif

    deTArray(void)
    :m_Length(0), m_Capacity(0), m_Items(NULL)  {}
    deTArray(const deTArray & RHS)
    :m_Length(RHS.m_Length),m_Capacity(RHS.m_Capacity)
    {
        if (m_Capacity > 0)
        {
            size_t i;
            m_Items = new T[m_Capacity];
            for (i = 0; i < m_Length; i++)
                m_Items[i] = RHS.m_Items[i];
        }
        else
            m_Items = NULL;
    }
    deTArray(size_t InitialSize)
    :m_Length(InitialSize),m_Capacity(InitialSize)
    {
        if (m_Capacity > 0)
            m_Items = new T[m_Capacity];
        else
            m_Items = NULL;
    }
    deTArray(size_t InitialSize,const T & Value)
    :m_Length(InitialSize),m_Capacity(InitialSize)
    {
        if (m_Capacity > 0)
        {
            u32 i;
            m_Items = new T[m_Capacity];
            for (i = 0; i < m_Length; i++)
                m_Items[i] = Value;
        }
        else
            m_Items = NULL;
    }
    ~deTArray()
    {
        if (m_Items != NULL)
        {
            delete [] m_Items;
            m_Items = NULL;
        }
    }

    deTArray <T> & operator=(const deTArray <T> & ref)
    {
        Resize(0);
        Resize(ref.m_Length);
        for (u32 i = 0; i < m_Length; ++i)
            m_Items[i] = ref.m_Items[i];

        return *this;
    }

    inline T& operator[](size_t ArrayItemIndex)         // L-value
    {
        #ifdef _DEBUG
        if (ArrayItemIndex < 0 || ArrayItemIndex >= m_Length)
        {
            // you've tried to access an invalid array element
            BREAK_EXECUTION();
        }
        #endif
        return m_Items[ArrayItemIndex];
    }
    inline const T& operator[](size_t ArrayItemIndex) const // R-value
    {
        #ifdef _DEBUG
        if (ArrayItemIndex < 0 || ArrayItemIndex >= m_Length)
        {
            // you've tried to access an invalid array element
            BREAK_EXECUTION();
        }
        #endif
        return m_Items[ArrayItemIndex];
    }
    inline iterator get_iterator(size_t ArrayItemIndex) const
    {
        return make_iterator(ArrayItemIndex);
    }
    
    inline deBoolean PushBack(const T& element)
    {
        int i = m_Length;
        if (m_Length >= m_Capacity)
        {
            // this will increment m_Length internally
            if (!Resize(m_Length+1))
                return deFALSE;
        }
        else
        {
            ++m_Length;
        }
        m_Items[i] = element;
        return deTRUE;
    }

    inline deBoolean InsertArrayQuick(const T* Array, size_t StartIndex, size_t NumElements)
    {
        if (StartIndex + NumElements > m_Length)
            return deFALSE;
        if (Array == NULL)
            return deFALSE;
        memcpy(&(m_Items[StartIndex]), Array, NumElements*sizeof(T));
        return deTRUE;
    }

    inline iterator IncrementSize()
    {
        if (Resize(m_Length+1))
            return make_iterator(m_Length-1);
        return end();
    }

    inline iterator IncrementSizeQuick(deBoolean ZeroMem = deFALSE)
    {
        if (ResizeQuick(m_Length+1, ZeroMem))
            return make_iterator(m_Length-1);
        return end();
    }
    
    deBoolean Reserve(size_t NewSize, deBoolean PrimitiveType = deFALSE)
    {
        size_t NewCapacity;
        NewCapacity = SmallestLargerPow2(NewSize);

        // if smaller but not by much, keep current capacity
        if (NewCapacity <= m_Capacity && NewCapacity >= m_Capacity/2)
            return deTRUE;

        T *NewItems;
        NewItems = new T[NewCapacity];

        if (NewItems == NULL)
            return deFALSE;
        
        if (m_Items)
        {
            if (PrimitiveType)
            {
                int i = min(m_Length, NewSize);
                memcpy(NewItems, m_Items, i * sizeof(T));
            }
            else
            {
                int k = min(m_Length, NewSize);
                for (int i=0; i < k; i++)
                {
                    NewItems[i] = m_Items[i];
                }
            }
            delete[] m_Items;
        }
        m_Capacity = NewCapacity;
        m_Items = NewItems;
        return deTRUE;
    }
    
    deBoolean Resize(size_t NewSize)
    {
        if (NewSize < 0)
            return deFALSE;

        if (NewSize == m_Length)
            return deTRUE;

        if (NewSize == 0)
        {
            m_Length = m_Capacity = 0;
            delete[] m_Items;
            m_Items = NULL;
            return deTRUE;
        }
        
        if (m_Capacity < NewSize)
        {
            if (!Reserve(NewSize))
                return deFALSE;
        }
        m_Length = NewSize;
        return deTRUE;
    }

    // WARNING!!!
    // Only use this method on primitive types in the array
    // such as int, char, etc. If you use this on a class that
    // maintains special information, it will most likely break.
    // Use Resize in those cases, as it deals with classes properly.
    // WARNING!!
    deBoolean ResizeQuick(size_t NewSize, deBoolean ZeroMem = deFALSE)
    {
        if (NewSize < 0)
            return deFALSE;

        if (NewSize == m_Length)
            return deTRUE;

        if (NewSize == 0)
        {
            m_Length = m_Capacity = 0;
            delete[] m_Items;
            m_Items = NULL;
            return deTRUE;
        }
        
        if (m_Capacity < NewSize)
        {
            if (!Reserve(NewSize, deTRUE))
                return deFALSE;
        }
        if (ZeroMem && NewSize > m_Length)
        {
            memset(m_Items + m_Length, 0, (NewSize - m_Length)*sizeof(T));
        }
        m_Length = NewSize;
        return deTRUE;
    }

    deBoolean RemoveElementAt(size_t index)
    {
        if (index < 0 || index >= m_Length)
        {
            DEBUGRETURN(deFALSE, "RemoveElementAt: Invalid array index");
        }

        int i;
        int NewSize = m_Length - 1;
        
        if (NewSize == 0)
        {
            m_Length = 0;
            return deTRUE;
        }

        for (i = index; i < NewSize; i++)
        {
            m_Items[i] = m_Items[i+1];
        }
        m_Length = NewSize;
        return deTRUE;
    }

    inline T* GetCArray() const { return m_Items; }

    inline size_t Length() const    { return m_Length; }
    
public:
    // STL compliance
    inline size_t size() const  { return m_Length; }
    inline size_t capacity()const   { return m_Capacity; }
    inline iterator begin() const { return make_iterator(0); }
    inline iterator end() const { return make_iterator(m_Length); }
    inline deBoolean resize(size_t NewSize) { return Resize(NewSize); }
    inline iterator push_back(const T& element) { PushBack(element); return get_iterator(m_Length-1); }
    inline iterator erase(iterator& it) { int index = iterator_index(it); RemoveElementAt(index); return make_iterator(index); }
};

#endif

---